package com.algorithm.cjm.jiaocai.ch4;

/**
 * 求数列的最大字段和
 * 给定 n 个元素的整数列 a1, a2,..., an。
 * 求形如：
 * ai, ai+1,...,aj    i,j = 1,...,n, i<= j 的字段，使其和为最大。
 * 当所有整数均为负整数时定义其最大字段和为0
 *
 * Created by jieming.chen on 2020/2/6
 */
public class Example15 {

    /**
     * 分治法
     *
     * @param a
     * @param n
     * @return
     */
    int max_sum(int a[], int n) {
        return max_sub_sum(a, 0, n);
    }

    /**
     * 分治法
     *
     * @param a
     * @param left
     * @param right
     * @return
     */
    int max_sub_sum(int a[], int left, int right) {
        int center, i, j, sum, left_sum, right_sum, s1, s2, lefts, rights;
        if (left == right) {
            if (a[left] > 0) {
                return a[left];
            } else {
                return 0;
            }
        } else {
            center = (left + right) / 2;
            left_sum = max_sub_sum(a, left, center);
            right_sum = max_sub_sum(a, center + 1, right);
            s1 = 0;
            lefts = 0;
            for (i = center; i >= left; i--) {
                lefts = lefts + a[i];
                if (lefts > s1) {
                    s1 = lefts;
                }
            }
            s2 = 0;
            rights = 0;
            for (i = center + 1; i <= right; i++) {
                rights = rights + a[i];
                if (rights > s2) {
                    s2 = rights;
                }
            }
            if (s1 + s2 < left_sum && right_sum < left_sum) {
                return left_sum;
            } else {
                return Math.max(s1 + s2, right_sum);
            }
        }
    }

    public static void main(String[] args) {
        Example15 example15 = new Example15();

        int[] arr = {-1, 0, 1, 2, 2, 1, -1};
        int[] arr1 = {1, 0, 1, -10, 2, -2, 1};
        int[] arr2 = {1, 0, 1, 2, 2, -2, 1};

        System.out.println(example15.max_sum(arr, 6));
        System.out.println(example15.max_sum(arr1, 6));
        System.out.println(example15.max_sum(arr2, 6));
    }

    int max_sum1(int a[]) {
        int n = a.length;
        int[][] res = new int[n][n];
        for (int i = 0; i < n; i++) {
            res[n-1][i] = Math.max(a[i], 0);
        }
        for (int i = n-2; i >= 0; i--) {
            for (int j = 0; j < i; j++) {
//                res[i] =
            }
        }


        return 0;
    }

}
